package code;

import java.util.ArrayList;
import java.util.Stack;

/*
 * 增加一个一维数组Min[i],记录当前的到栈顶最小的元素，Min[i]=min(x,Min[i-1])递推
 */
public class MinStack {
	
	private Stack<Integer> stack=new Stack<>();
	
	private ArrayList min=new ArrayList<Integer>();
	
	public void push(int x){
		stack.push(x);
		if(min.size()==0)	min.add(x);
		else{
			int y=(int) min.get(min.size()-1);
			x=x<y?x:y;
			min.add(x);
		}
	}
	public void pop(){
		stack.pop();
		min.remove(min.size()-1);
	}
	public int top(){
		return stack.peek();
	}
	public int getMin(){
		return (int) min.get(min.size()-1);
	}
}
